class Solution {//leetcode30——串联所有单词的子串
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;
        int len=words[0].size();
        for(auto& e:words){
            hash1[e]++;
        }
        
        for(int i=0;i<len;i++){
            unordered_map<string,int> hash2;
            int all=0;//hash2中映射的总个数
            int cnt=0;
            for(int left=i,right=left;right+len<=s.size();right+=len){
                //进窗口
                string sub=s.substr(right,len);
                hash2[sub]++;
                all++;
                if(hash2[sub]<=hash1[sub]) cnt++;
                //出窗口
                if(all>words.size()){
                    string out;
                    out=s.substr(left,len);
                    
                    if(hash2[out]<=hash1[out]) cnt--;
                    hash2[out]--;
                    left+=len;
                    all--;
                }
                
                if(cnt==words.size()) ret.push_back(left);
            }
        }
        return ret;
    }
};